package BinaryTree;
// 98-验证二叉搜索树-middle
// 二叉搜索树中序遍历为升序序列

import java.util.ArrayDeque;
import java.util.Scanner;

public class IsValidBST {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }    
    public static boolean isValidBST(TreeNode root){
        // 提前拦截特殊情况
        if(root == null) return true;
        if(root.left == null && root.right == null) return true;
        return valid(root);
    }
    // pre节点
    private static TreeNode pre = null;
    private static boolean valid(TreeNode root){
        // 递归终止条件
        if(root == null) return true;
        // 递归left
        boolean left = valid(root.left);
        // 和pre比较
        if(pre != null && root.val <= pre.val) return false;
        // 更新pre
        pre = root;
        boolean right = valid(root.right);
        return left && right;
    }
    public static TreeNode buildTree(String[] nodes){
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null")) 
            return null;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        int index = 1;
        while(index < nodes.length && !queue.isEmpty()){
            TreeNode node = queue.poll();
            if(index < nodes.length && !nodes[index].equals("null")){
                node.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.left);
            }
            index++;
            if(index < nodes.length && !nodes[index].equals("null")){
                node.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.right);
            } 
            index++;
        }
        return root;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nodes = sc.nextLine().split(",");
        TreeNode root = buildTree(nodes);
        System.out.println(isValidBST(root));
        sc.close();
    }
}
